1. Field of Invention
The present invention pertains to the field of software compilers. More particularly, this invention relates to flexible scheduling of non-speculative instructions in a code sequence.
2. Art Background
Computer systems typically contain one or more processors that perform instruction execution. Such a processor may also be referred to as a central processing unit (CPU) or a host processor. A processor usually performs a variety of tasks in the computer system under control of a set of software programs. For example, such software programs typically include application programs, hardware driver programs, and operating system code for the computer system.
Such software programs may be written in one or more of a variety of programming languages. Such programming languages include higher order programming languages such as the C programming language as well as lower level assembly code languages which are specific to a particular processor architecture. Such programming languages are typically employed to define a program sequence of instructions for a software program in a human readable format. Such a program sequence of human readable instructions may be referred to as program source code.
Software compilers are typically employed to translate such program source code into a set of instructions suitable for consumption by a particular target processor. The instructions generated by such a software compiler may be referred to as object code or executable code or machine code. The instructions consumed by a target processor usually include instructions for performing memory read operations, memory write operations, arithmetic operations and conditional branch operations.
In addition, prior software compilers typically schedule the instructions in object code for execution. Typically, a software compiler schedules instructions in the object code by arranging the sequence of instructions in a particular manner. For example, a prior software compiler may schedule a particular instruction for execution prior to a branch instruction by moving the particular instructions upward to an earlier point of a program sequence in relation to the branch instruction.
Typically, an instruction that may be moved upward across a condition branch instruction without violating the correct execution of the program source code is referred to as a speculative instruction. For example, such speculative instructions include some read instructions and some arithmetic instructions. Non-speculative instructions, on the other hand, are instructions that cannot be moved upward across conditional branch instructions without violating the logic of the program source code. Such non-speculative instructions are said to be guarded by the conditional branch instruction. Examples of such a non-speculative instructions include store memory instructions and other conditional branch instructions.
Prior software compilers commonly perform scheduling optimizations to suit the architecture of a particular target processor. Such scheduling optimizations by prior software compilers usually includes the movement of speculative instructions within the object code. However, prior software compilers usually cannot move non-speculative instructions upward across other non-speculative instructions such as conditional branch instructions without violating the logic of the original source code. Unfortunately, such limits on the movement of non-speculative instructions limits the flexibility and effectiveness of prior scheduling optimization techniques.
Moreover, a target processor that consumes code generated by prior software compilers usually executes conditional branch instructions serially due to the lack of scheduling optimization. Such a serial execution of conditional branch instructions is extremely time-consuming because the target processor typically computes a branch target address for each conditional branch instruction whether or not the branch is taken. Such time consuming branch operations usually slow the overall throughput of the target processor even though in typical code sequences many of the conditional branches are rarely taken.